/*
 * @Author: 缄默
 * @Date: 2022-04-13 15:12:30
 * @LastEditors: 缄默
 * @LastEditTime: 2022-04-13 15:50:28
 */

//堆排序实现

#include <iostream>
#include <vector>

using namespace std;

void heapSort(vector<int>& arr);
void FilterDown(vector<int>& arr, int i, int EndOfHeap);


int main() {
    vector<int> arr({3, 1, 2, 4, 6, 8});
    heapSort(arr);
    for (auto i : arr) {
        cout << i << " ";
    }
    return 0;
}

void heapSort(vector<int>& arr) {
    if (arr.size() == 0) return ;
    int length = arr.size();
    for (int i = length / 2 - 1; i >= 0; i--) FilterDown(arr, i, length - 1);
    for (int i = length - 1; i >= 1; i--) {
        swap(arr[0], arr[i]);
        FilterDown(arr, 0, i - 1);
    }

}

void FilterDown(vector<int>& arr, int i, int EndOfHeap) {
    int current = i;
    int child = 2 * i + 1;
    int temp = arr[i];
    while (child <= EndOfHeap) {
        if (child + 1 <= EndOfHeap && arr[child] < arr[child + 1]) {
            child = child + 1;
        }
        if (temp >= arr[child]) break;
        else {
            arr[current] = arr[child];
            current = child;
            child = 2 * child + 1;
        }
    }
    arr[current] = temp;
}
